Stack Data Structure
Codes:
- Method 1 using List
- Method 2 using deque
This track of the course covers the topic "Stack".
In details, this track will cover:
Objective: The objective of this track is to familiarize the learners with Stack.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
This video discusses the various applications of Stack.
This video discusses the implementation of Stack in C++.
Code:
In this video we'll talk about stack in java collections
Code:
This video discusses the below problem:
Given a string of parenthesis ({, }, (, ), [ and ]), we need to check if this string is balanced or not.
Code:
This video discusses the problem of implementation of Two stacks in a single array.
Codes:
This video discusses the problem of implementation of K Stacks in an array
Codes:
This video discusses the problem of Stock span problem along with few variations.
Codes:
This video discusses the below problem:
Given an array of distinct integers, find the closest (positive wise) greater on left of every element. If there is no greater element on l;eft, then print -1
Codes:
This video discusses the below problem:
Given an array of distinct integers, find the NextGreater(position-wise closest and on the right side) of every array elements.
Codes:
This video discusses the first part of the problem of calculating the Largest Rectangular Area in a Histogram.
Codes:
This video discusses the second part of the problem of calculating the Largest Rectangular Area in a Histogram.
Codes:
Design a stack that supports normal stack operatiosn in O(1) and also supprots getMin() in O(1)
Codes:
Infix, prefix and Postfix are three different ways to write mathematical expressions. This video introduces these three and talks about their advantages/distadvantages.
This video talks about simple method for Infix to Postfix conversion.
This video talks about infix to postfix conversion using stack.
This video talks about a simple, efficient and stack based solution for evaluation of postfix.
This video talks about simple method for Infix to Prefix Conversion.
This video talks about stack based efficient solution for Infix to Prefx conversion.
This method talks about simple, efficient and stack based solution for evaluation of prefix.

How to understand a stack practically?
There are many real-life examples of a stack. Consider the simple example of plates stacked over one another in a canteen. The plate that is at the top is the first one to be removed, i.e. the plate that has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO/FILO order.Implementing Stack using Arrays
/* C++ program to implement basic stack operations */
#include<bits/stdc++.h>
using namespace std;
#define MAX 1000
class Stack
{
int top;
public:
int a[MAX]; //Maximum size of Stack
Stack() { top = -1; }
bool push(int x);
int pop();
bool isEmpty();
};
bool Stack::push(int x)
{
if (top >= (MAX-1))
{
cout << "Stack Overflow";
return false;
}
else
{
a[++top] = x;
cout<<x <<" pushed into stack\n";
return true;
}
}
int Stack::pop()
{
if (top < 0)
{
cout << "Stack Underflow";
return 0;
}
else
{
int x = a[top--];
return x;
}
}
bool Stack::isEmpty()
{
return (top < 0);
}
// Driver program to test above functions
int main()
{
class Stack s;
s.push(10);
s.push(20);
s.push(30);
cout<<s.pop() << " Popped from stack\n";
return 0;
}
/* Java program to implement basic stack operations */
class Stack
{
static final int MAX = 1000;
int top;
int a[] = new int[MAX]; // Maximum size of Stack
boolean isEmpty()
{
return (top < 0);
}
Stack()
{
top = -1;
}
boolean push(int x)
{
if (top >= (MAX-1))
{
System.out.println("Stack Overflow");
return false;
}
else
{
a[++top] = x;
System.out.println(x + " pushed into stack");
return true;
}
}
int pop()
{
if (top < 0)
{
System.out.println("Stack Underflow");
return 0;
}
else
{
int x = a[top--];
return x;
}
}
}
// Driver code
class Main
{
public static void main(String args[])
{
Stack s = new Stack();
s.push(10);
s.push(20);
s.push(30);
System.out.println(s.pop() + " Popped from stack");
}
}
10 pushed into stack
20 pushed into stack
30 pushed into stack
30 popped from stack
Implementing Stack using Linked List
// C++ program for linked list implementation of stack
#include <bits/stdc++.h>
using namespace std;
// A structure to represent a stack
struct StackNode
{
int data;
struct StackNode* next;
};
// Utility function to create new stack node
struct StackNode* newNode(int data)
{
struct StackNode* stackNode = new StackNode;
stackNode->data = data;
stackNode->next = NULL;
return stackNode;
}
// Function to check if the Stack is empty
int isEmpty(struct StackNode *root)
{
return !root;
}
// Function to push a new element onto Stack
void push(struct StackNode** root, int data)
{
struct StackNode* stackNode = newNode(data);
stackNode->next = *root;
*root = stackNode;
cout<<data<<" pushed to stack\n";
}
// Function to pop element from Stack
int pop(struct StackNode** root)
{
if (isEmpty(*root))
return INT_MIN;
struct StackNode* temp = *root;
*root = (*root)->next;
int popped = temp->data;
free(temp);
return popped;
}
// Function to get the element present
// at top of stack
int peek(struct StackNode* root)
{
if (isEmpty(root))
return INT_MIN;
return root->data;
}
// Driver Code
int main()
{
struct StackNode* root = NULL;
push(&root, 10);
push(&root, 20);
push(&root, 30);
printf("%d popped from stack\n", pop(&root));
printf("Top element is %d\n", peek(root));
return 0;
}
// Java Code for Linked List Implementation
// of Stacks
public class StackAsLinkedList {
StackNode root;
static class StackNode {
int data;
StackNode next;
StackNode(int data) {
this.data = data;
}
}
public boolean isEmpty() {
if (root == null) {
return true;
} else return false;
}
public void push(int data) {
StackNode newNode = new StackNode(data);
if (root == null) {
root = newNode;
} else {
StackNode temp = root;
root = newNode;
newNode.next = temp;
}
System.out.println(data + " pushed to stack");
}
public int pop() {
int popped = Integer.MIN_VALUE;
if (root == null) {
System.out.println("Stack is Empty");
} else {
popped = root.data;
root = root.next;
}
return popped;
}
public int peek() {
if (root == null) {
System.out.println("Stack is empty");
return Integer.MIN_VALUE;
} else {
return root.data;
}
}
public static void main(String[] args) {
StackAsLinkedList sll = new StackAsLinkedList();
sll.push(10);
sll.push(20);
sll.push(30);
System.out.println(sll.pop() + " popped from stack");
System.out.println("Top element is " + sll.peek());
}
}
10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack
Top element is 20
Pros: The linked list implementation of stack can either grow or shrink according to the needs at runtime.
Cons: Requires extra memory due to involvement of pointers.
stack< data_type > stack_name;
Here,
data_type: This defines the type of data to be
stored in the stack.
stack_name: This specifies the name of the stack.
The stack is : 1 5 20 30 10
s.size() : 5
s.top() : 1
s.pop() : 5 20 30 10

Pop :
4
3
2
1
0
Element on stack top : 4
Element is found at position 3
Element not found
a op1 b op2 c op3 dThe compiler first scans the expression to evaluate the expression b * c, then again scan the expression to add a to it. The result is then added to d after another scan.
If op1 = +, op2 = *, op3 = +
// C++ implementation to convert infix expression
// to equivalent postfix expression
// Note that here we have used
// std::stack for Stack operations
#include<bits/stdc++.h>
using namespace std;
// Function to return precedence of operators
int prec(char c)
{
if(c == '^')
return 3;
else if(c == '*' || c == '/')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return -1;
}
// The main function to convert infix
// expression to postfix expression
void infixToPostfix(string s)
{
stack<char> st;
st.push('N');
int l = s.length();
string ns;
for(int i = 0; i < l; i++)
{
// If the scanned character is an operand,
// add it to output string.
if((s[i] >= 'a' && s[i] <= 'z')||
(s[i] >= 'A' && s[i] <= 'Z'))
ns+=s[i];
// If the scanned character is an ‘(‘,
// push it to the stack.
else if(s[i] == '(')
st.push('(');
// If the scanned character is an ‘)’,
// pop and to output string from the stack
// until an ‘(‘ is encountered.
else if(s[i] == ')')
{
while(st.top() != 'N' && st.top() != '(')
{
char c = st.top();
st.pop();
ns += c;
}
if(st.top() == '(')
{
char c = st.top();
st.pop();
}
}
// If an operator is scanned
else{
while(st.top() != 'N' && prec(s[i]) <= prec(st.top()))
{
char c = st.top();
st.pop();
ns += c;
}
st.push(s[i]);
}
}
// Pop all the remaining elements from the stack
while(st.top() != 'N')
{
char c = st.top();
st.pop();
ns += c;
}
cout << ns << endl;
}
// Driver Code
int main()
{
string exp = "a+b*(c^d-e)^(f+g*h)-i";
infixToPostfix(exp);
return 0;
}
// Java implementation to convert infix expression
// to equivalent postfix expression
// Note that here we have used the Stack class
// for all Stack operations
import java.util.Stack;
class Test
{
// A utility function to return precedence
// of a given operator
// Higher the returned value means
// higher the precedence
static int Prec(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
// The main method that converts given
// infix expression to postfix expression.
static String infixToPostfix(String exp)
{
// initializing empty String for result
String result = new String("");
// initializing empty stack
Stack<Character> stack = new Stack<>();
for (int i = 0; i<exp.length(); ++i)
{
char c = exp.charAt(i);
// If the scanned character is an operand,
// add it to output.
if (Character.isLetterOrDigit(c))
result += c;
// If the scanned character is an '(',
// push it to the stack.
else if (c == '(')
stack.push(c);
// If the scanned character is an ')',
// pop and output from the stack
// until an '(' is encountered.
else if (c == ')')
{
while (!stack.isEmpty() && stack.peek() != '(')
result += stack.pop();
if (!stack.isEmpty() && stack.peek() != '(')
return "Invalid Expression"; // invalid expression
else
stack.pop();
}
else // an operator is encountered
{
while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek()))
result += stack.pop();
stack.push(c);
}
}
// pop all the operators from the stack
while (!stack.isEmpty())
result += stack.pop();
return result;
}
// Driver method
public static void main(String[] args)
{
String exp = "a+b*(c^d-e)^(f+g*h)-i";
System.out.println(infixToPostfix(exp));
}
}
Output: abcd^e-fgh*+^*+i-
// C++ program to evaluate value of
// a postfix expression
#include <iostream>
#include <string.h>
#include<stack>
using namespace std;
// Function that returns the value of a
// given postfix expression
int evaluatePostfix(char* exp)
{
// Create a stack
stack<int> st;
int i;
// Scan all characters one by one
for (i = 0; exp[i]; ++i)
{
// If the scanned character is an operand (number here),
// push it to the stack.
if (isdigit(exp[i]))
st.push(exp[i] - '0');
// If the scanned character is an operator, pop two
// elements from stack apply the operator
else
{
int val1 = st.top();
st.pop();
int val2 = st.top();
st.pop();
switch (exp[i])
{
case '+': st.push(val2 + val1); break;
case '-': st.push(val2 - val1); break;
case '*': st.push(val2 * val1); break;
case '/': st.push(val2/val1); break;
}
}
}
return st.top();
}
// Driver Code
int main()
{
char exp[] = "231*+9-";
cout<<"postfix evaluation: "<< evaluatePostfix(exp);
return 0;
}
// Java proram to evaluate value of a postfix expression
import java.util.Stack;
public class Test
{
// Method to evaluate value of a postfix expression
static int evaluatePostfix(String exp)
{
// create a stack
Stack<Integer> stack=new Stack<>();
// Scan all characters one by one
for(int i=0;i<exp.length();i++)
{
char c=exp.charAt(i);
// If the scanned character is an operand (number here),
// push it to the stack.
if(Character.isDigit(c))
stack.push(c - '0');
// If the scanned character is an operator, pop two
// elements from stack apply the operator
else
{
int val1 = stack.pop();
int val2 = stack.pop();
switch(c)
{
case '+':
stack.push(val2+val1);
break;
case '-':
stack.push(val2- val1);
break;
case '/':
stack.push(val2/val1);
break;
case '*':
stack.push(val2*val1);
break;
}
}
}
return stack.pop();
}
// Driver program to test above functions
public static void main(String[] args)
{
String exp="231*+9-";
System.out.println("postfix evaluation: "+evaluatePostfix(exp));
}
}output: postfix evaluation: -4
// CPP program to evaluate value of a postfix
// expression having multiple digit operands
#include <bits/stdc++.h>
using namespace std;
// Function that returns value
// of a given postfix expression
int evaluatePostfix(char* exp)
{
// Create a stack
stack<int> st;
int i;
// Scan all characters one by one
for (i = 0; exp[i]; ++i)
{
// if the character is blank space then continue
if(exp[i] == ' ')continue;
// If the scanned character is an
// operand (number here), extract the full number
// Push it to the stack.
else if (isdigit(exp[i]))
{
int num=0;
// extract full number
while(isdigit(exp[i]))
{
num = num * 10 + (int)(exp[i] - '0');
i++;
}
i--;
// push the element in the stack
st.push(num);
}
// If the scanned character is an operator, pop two
// elements from stack apply the operator
else
{
int val1 = st.top();
st.pop();
int val2 = st.top();
st.pop();
switch (exp[i])
{
case '+': st.push(val2 + val1); break;
case '-': st.push(val2 - val1); break;
case '*': st.push(val2 * val1); break;
case '/': st.push(val2/val1); break;
}
}
}
return st.top();
}
// Driver code
int main()
{
char exp[] = "100 200 + 2 / 5 * 7 +";
cout << evaluatePostfix(exp);
return 0;
}
// Java proram to evaluate value of a postfix
// expression having multiple digit operands
import java.util.Stack;
class Test1
{
// Method to evaluate value of a postfix expression
static int evaluatePostfix(String exp)
{
//create a stack
Stack<Integer> stack = new Stack<>();
// Scan all characters one by one
for(int i = 0; i < exp.length(); i++)
{
char c = exp.charAt(i);
if(c == ' ')
continue;
// If the scanned character is an operand
// (number here),extract the number
// Push it to the stack.
else if(Character.isDigit(c))
{
int n = 0;
//extract the characters and store it in num
while(Character.isDigit(c))
{
n = n*10 + (int)(c-'0');
i++;
c = exp.charAt(i);
}
i--;
//push the number in stack
stack.push(n);
}
// If the scanned character is an operator, pop two
// elements from stack apply the operator
else
{
int val1 = stack.pop();
int val2 = stack.pop();
switch(c)
{
case '+':
stack.push(val2+val1);
break;
case '-':
stack.push(val2- val1);
break;
case '/':
stack.push(val2/val1);
break;
case '*':
stack.push(val2*val1);
break;
}
}
}
return stack.pop();
}
// Driver program to test above functions
public static void main(String[] args)
{
String exp = "100 200 + 2 / 5 * 7 +";
System.out.println(evaluatePostfix(exp));
}
}
757
// C++ program to implement two stacks
// in one Array
#include<iostream>
#include<stdlib.h>
using namespace std;
class twoStacks
{
int *arr;
int size;
int top1, top2;
public:
twoStacks(int n) // constructor
{
size = n;
arr = new int[n];
top1 = -1;
top2 = size;
}
// Method to push an element x to stack1
void push1(int x)
{
// There is at least one empty space for new element
if (top1 < top2 - 1)
{
top1++;
arr[top1] = x;
}
else
{
cout << "Stack Overflow";
exit(1);
}
}
// Method to push an element x to stack2
void push2(int x)
{
// There is at least one empty space
// for new element
if (top1 < top2 - 1)
{
top2--;
arr[top2] = x;
}
else
{
cout << "Stack Overflow";
exit(1);
}
}
// Method to pop an element from first stack
int pop1()
{
if (top1 >= 0 )
{
int x = arr[top1];
top1--;
return x;
}
else
{
cout << "Stack UnderFlow";
exit(1);
}
}
// Method to pop an element from second stack
int pop2()
{
if (top2 < size)
{
int x = arr[top2];
top2++;
return x;
}
else
{
cout << "Stack UnderFlow";
exit(1);
}
}
};
// Driver Program
int main()
{
twoStacks ts(5);
ts.push1(5);
ts.push2(10);
ts.push2(15);
ts.push1(11);
ts.push2(7);
cout << "Popped element from stack1 is " << ts.pop1();
ts.push2(40);
cout << "\nPopped element from stack2 is " << ts.pop2();
return 0;
}
// Java program to implement two stacks in a
// single array
class TwoStacks
{
int size;
int top1, top2;
int arr[];
// Constructor
TwoStacks(int n)
{
arr = new int[n];
size = n;
top1 = -1;
top2 = size;
}
// Method to push an element x to stack1
void push1(int x)
{
// There is at least one empty space for
// new element
if (top1 < top2 - 1)
{
top1++;
arr[top1] = x;
}
else
{
System.out.println("Stack Overflow");
System.exit(1);
}
}
// Method to push an element x to stack2
void push2(int x)
{
// There is at least one empty space for
// new element
if (top1 < top2 -1)
{
top2--;
arr[top2] = x;
}
else
{
System.out.println("Stack Overflow");
System.exit(1);
}
}
// Method to pop an element from first stack
int pop1()
{
if (top1 >= 0)
{
int x = arr[top1];
top1--;
return x;
}
else
{
System.out.println("Stack Underflow");
System.exit(1);
}
return 0;
}
// Method to pop an element from second stack
int pop2()
{
if(top2 < size)
{
int x =arr[top2];
top2++;
return x;
}
else
{
System.out.println("Stack Underflow");
System.exit(1);
}
return 0;
}
// Driver program to test twoStack class
public static void main(String args[])
{
TwoStacks ts = new TwoStacks(5);
ts.push1(5);
ts.push2(10);
ts.push2(15);
ts.push1(11);
ts.push2(7);
System.out.println("Popped element from" +
" stack1 is " + ts.pop1());
ts.push2(40);
System.out.println("Popped element from" +
" stack2 is " + ts.pop2());
}
}Popped element from stack1 is 11
Popped element from stack2 is 40
[1 2 3 4 5]Solution - We will traverse the linked list and push all the nodes of the linked list to the stack. Since stack have property of Last In, First Out, List is automatically reversed when we will pop the stack elements one by one.
[5 4 3 2 1]
void printreverse(Node *head)Time Complexity : O(n)
{
stack < Node* > s
current = head
while(current != NULL)
{
s.push(current)
current = current->next
}
while( ! s.empty())
{
node = s.top()
print(node->data)
s.pop()
}
}
Input : [ ( ) ] { } { [ ( ) ( ) ] ( ) }
Output : true
Input : [ ( ] )
Output : false
Solution : Follow the streps below -// function to check if paranthesis are balancedTime Complexity : O(n)
bool areParanthesisBalanced(string expr)
{
stack < char > s
for i=0 to expr.size() {
if (expr[i]=='('||expr[i]=='['||expr[i]=='{') {
s.push(expr[i])
continue
}
// stack can not be empty for closing bracket
if s.empty()
return false
switch (expr[i]) {
case ')': {
x = s.top()
s.pop()
if (x=='{' || x=='[')
return false
break
}
case '}': {
x = s.top();
s.pop();
if (x=='(' || x=='[')
return false
break
}
case ']': {
x = s.top();
s.pop();
if (x =='(' || x == '{')
return false
break
}
}
}
// Check Empty Stack
return (s.empty())
}
Input : [13, 7, 6, 12]Solution : Follow the below steps -
Output
Element NGE
13 --> -1
7 --> 12
6 --> 12
12 --> -1
// Next greater ElementTime Complexity : O(n)
void printNGE(arr, n)
{
stack < int > s
s.push(arr[0])
for i=0 to n-1 {
if (s.empty()) {
s.push(arr[i])
continue
}
while (s.empty() == false && s.top() < arr[i]) {
print(s.top() + "-->" + arr[i])
s.pop()
}
s.push(arr[i])
while (s.empty() == false) {
print(s.top() + "-->" + -1)
s.pop()
}
}
}
A | O(n logk) |
B | O(nk) |
C | O(n<sup>2</sup>) |
D | O(k<sup>2</sup>) |